#include "stack_queue.h"
#include<iostream>
#include<string>
#include<cctype>
using namespace std;

//listnode
listNode::listNode() : next(NULL), data(0) {}
listNode::listNode(int nodeData, listNode* succ) : next(succ), data(nodeData) {}

//栈初始化
MyStack::MyStack() : topNode(NULL), stackSize(0) {}

//销毁栈
MyStack::~MyStack() {
    while (topNode != NULL) {
        listNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }
}

//入栈
bool MyStack::push(const int& item) {
    listNode* newNode = new listNode(item, topNode);
    if (!newNode) return false;
    topNode = newNode;
    stackSize++;
    return true;
}

//出栈
bool MyStack::pop(int& item) {
    if (topNode == NULL) return false;
    listNode* temp = topNode;
    item = topNode->data;
    topNode = topNode->next;
    delete temp;
    stackSize--;
    return true;
}

//返回栈顶元素
bool MyStack::getTop(int& item) {
    if (topNode == NULL) return false;
    item = topNode->data;
    return true;
}

//队列初始化
MyQueue::MyQueue(const int& cap) {
    capacity = cap + 1;
    queue = new int[capacity];
    front = rear = 0;
}

//队列删除
MyQueue::~MyQueue(){
    delete[] queue;
}

//isfull
bool MyQueue::isFull() {
    return (rear + 1) % capacity == front;
}

//入队
bool MyQueue::enQueue(const int& item) {
    if (isFull()) return false;
    queue[rear] = item;
    rear = (rear + 1) % capacity;
    return true;
}

//出队
bool MyQueue::deQueue(int& item) {
    if (front == rear) return false;
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

//返回队头元素
bool MyQueue::getFront(int& item) {
    if (front == rear) return false;
    item = queue[front];
    return true;
}

//中缀转后缀
int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

bool postfixExpression(const string& infix, string& result) {
    MyStack opStack;
    result = "";
    
    for (size_t i = 0; i < infix.length(); i++) {
        char ch = infix[i];
        
        if (isdigit(ch)) {
            result += ch;
        }
        else if (ch == '(') {
            opStack.push(ch);
        }
        else if (ch == ')') {
            int topOp;
            while (opStack.getTop(topOp) && (char)topOp != '(') {
                result += (char)topOp;
                opStack.pop(topOp);
            }
            if (!opStack.getTop(topOp) || (char)topOp != '(') {
                result = "Expression is wrong!";
                return false;
            }
            opStack.pop(topOp);
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            int topOp;
            while (opStack.getTop(topOp) && (char)topOp != '(' && 
                   getPriority((char)topOp) >= getPriority(ch)) {
                result += (char)topOp;
                opStack.pop(topOp);
            }
            opStack.push(ch);
        }
        else if (ch == ' ') {
            continue;
        }
        else {
            result = "Expression is wrong!";
            return false;
        }
    }
    
    int topOp;
    while (opStack.pop(topOp)) {
        if ((char)topOp == '(') {
            result = "Expression is wrong!";
            return false;
        }
        result += (char)topOp;
    }
    
    return true;
}

//求值
bool expressionVal(const string& expr, int& result) {
    string postfix;
    if (!postfixExpression(expr, postfix)) {
        result = 0;
        return false;
    }
    
    if (postfix == "Expression is wrong!") {
        result = 0;
        return false;
    }
    
    MyStack numStack;
    
    for (size_t i = 0; i < postfix.length(); i++) {
        char ch = postfix[i];
        
        if (isdigit(ch)) {
            numStack.push(ch - '0');
        }
        else {
            int right, left;
            if (!numStack.pop(right) || !numStack.pop(left)) {
                result = 0;
                return false;
            }
            
            switch (ch) {
                case '+': numStack.push(left + right); break;
                case '-': numStack.push(left - right); break;
                case '*': numStack.push(left * right); break;
                case '/': 
                    if (right == 0) {
                        result = 0;
                        return false;
                    }
                    numStack.push(left / right); 
                    break;
                default:
                    result = 0;
                    return false;
            }
        }
    }
    
    if (!numStack.pop(result)) {
        result = 0;
        return false;
    }
    
    return true;
}

//杨辉三角
void yanghui(const int& n) {
    if (n <= 0) return;
    
    MyQueue q(n + 2);
    q.enQueue(1);
    
    for (int i = 1; i <= n; i++) {
        int s = 0;
        q.enQueue(0);
        
        for (int j = 0; j < i + 1; j++) {
            int t;
            q.deQueue(t);
            int x = s + t;
            q.enQueue(x);
            s = t;
            
            if (j > 0) cout << ",";
            cout << x;
        }
        cout << endl;
    }
}


void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}



